/**
 * 397.整数替换
 */
public class Exerciser6 {
    public int integerReplacement(int n) {
        long m = n;
        int ans = 0;
        while(m != 1) {
            if(m % 2 == 0) {
                // 偶数
                m /= 2;
            }else {
                // 奇数
                // 分成两种情况：
                //1: 某个奇数的最后一段为 01，比如：10000001 -> 最好的方法就是-1 -> 10000000 ->  之后进行除2就是最快的
                //2: 某个奇数的最后一段为 11，比如：00001111 -> 最好的方法就是+1 -> 00010000 ->  之后进行除2就是最快的
                // 特殊的情况是 n为3的时候，0011 -> 最好的是-1 -> 0010 -> 之后除2就是最快速的 -> 1
                if(m != 3 && ((m >> 1) & 1) == 1) {
                    // 这个就是判断m的二进制中最后的两位中第二位 是1还是0
                    m++;
                }else {
                    m--;
                }
            }
            ans++;
        }
        return ans;
    }
}
